package test.algorithm.FastSlowPointer;

/**
 * 归并排序
 * @author serenity
 *
 */
public class MergeSort {
	
	/**
	 * 归并排序（递归调用）
	 * @param list
	 * @param low 起始位置
	 * @param upper 结束位置
	 */
	public static void mergeSort(int[] list, int low,int upper){
		
		//起始位置和结束位置不一样时（即有多个元素）
		if(low!=upper){
			int mid = (low+upper)/2;
			
			//对左边数组进行递归
			mergeSort(list,low,mid);
			//对右边数组进行递归 
			mergeSort(list,mid+1,upper);
			
			//归并
			merge(list,low,mid,upper);
		}
	}
	
	/**
	 * 归并
	 * @param list
	 * @param low 起始位置
	 * @param mid 分割位置（中间分割）
	 * @param upper 结束位置
	 */
	public static void merge(int[] list,int low,int mid,int upper){
		//存储临时排序序列
		int[] temp = new int[list.length];
		
		//左半段序列起始位置
		int leftIndex = low ;
		//右半段序列起始位置
		int rightIndex = mid+1;
		//临时序列的存储位置
		int k=0;
		
		//左右序列都有元素的情况
		while(leftIndex <= mid && rightIndex <= upper ){
			//从两个数组中取出最小的放入中间数组
			if(list[leftIndex]<list[rightIndex]){
				//左序列索引位置值比右序列索引位置小，
				//则左序列索引位置元素插入temp后
				//左索引自增，k自增
				temp[k++] = list[leftIndex++];
			}else{
				//左序列索引位置值比右序列索引位置大，
				//则右序列索引位置元素插入temp后
				//右索引自增，k自增
				temp[k++] = list[rightIndex++];
			}
		}
		
		//右序列已插入完毕，左序列还没有插入完的情况
		while(leftIndex <= mid){
			temp[k++] = list[leftIndex++];
		}
		
		//左序列已插入完毕，右序列还没有插入完的情况
		while(rightIndex <= upper){
			temp[k++] = list[rightIndex++];
		}
		
		//将排序号的temp序列元素添加到list的对应位置
		int size = upper-low+1;
		for(int i = 0;i<size;i++){
			list[low+i] = temp[i];
		}
		
	}

	
	public static void main(String[] args) {
		int[] a = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};

		mergeSort(a,0,a.length-1);
		
		System.out.print("归并排序：");
		for(int i : a){
			System.out.print(i+" ");
		}
	}

}
